/*
 * Program Homework 1 Prefix Sum OpenMP
 * Name: Songgang Xu
 * Email: sxu@tamu.edu
 */

/*
 * Prefix_sum.openmp.c - Description:
 * Compute prefix_sum using OpenMP
 * User specifiy the number of integers 
 * User specify the number of processors
 * Program generate the integers parallelly
 * Output the sum of all the integers
 */


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/resource.h>
#include <omp.h>


/*
 * printElapsed (calculate & print out time elapsed)
 */
void printElapsed (char *desc, struct timeval *start, struct timeval *end, int niters) 
{
	struct timeval elapsed;
	if (start -> tv_usec > end -> tv_usec) 
	{
		end -> tv_usec += 1000000;
		end -> tv_sec--;
	}

	elapsed.tv_usec = end -> tv_usec - start -> tv_usec;
	elapsed.tv_sec = end -> tv_sec - start -> tv_sec;

	printf("\n %s total elapsed time = %1d (usec)",
		   desc, (elapsed.tv_sec*1000000 + elapsed.tv_usec)/niters);

}/* printElapsed() */





/*
 * Main function (parallel computing prefix sums)
 */
int main (int argc, char * argv[]) {

	int numints = 0;                  /* num of integers */
	int numthreads = 0;               /* num of threads */

	int * integers = NULL;             /* memory for the random integers */
	int * predec = NULL;              /* pointer to memory to record predecssor of element */

	struct timeval tmstart, tmend;    
	struct timeval genstart, genend;  
	struct timezone tzp; 

	/*----------------------------------------------------------------
	 * Check arguments
	 *---------------------------------------------------------------*/
	if (argc < 2) 
	{
		printf("Usage : %s [numints]\n", argv[0]);
		return 0;
	}
	numthreads = omp_get_max_threads();
	if (numthreads > 256) 
	{
		printf("Usage : %s [numints]\n - threads overflow. Maxium number of threads is 256.", argv[0]);
		return 0;
	}

	numints = atoi(argv[1]);
	printf("\nnumthreads = %d, numints = %d\nExcuting %s ...\n", omp_get_max_threads(), numints, argv[0]);
	/*----------------------------------------------------------------
	 * allocate shared memory
	 *---------------------------------------------------------------*/
	integers = (int *) malloc(sizeof(int) * numints);
	predec = (int *) malloc(sizeof(int) * numints);

	if (!integers || !predec) 
	{
		printf("\nMaster Process - unable to malloc()\n");
		return 1;
	}

	/*---------------------------------------------------------------
	 * get initial index of predecessor of each element
	 *-------------------------------------------------------------*/
	predec[0] = -1;
	for (int j = numints - 1; j > 0; j--) 
	{
		predec[j] = j - 1;
	}

	gettimeofday(&genstart, &tzp);

	/*---------------------------------------------------------------
	 * generate the random integers in parallel
	 *--------------------------------------------------------------*/
#pragma omp parallel shared(integers, numints)
	{
		int tid;                            
		int numelts;                       /* num of elements one thread computes */
		int nthreads;                      /* total number of threads requested */
		int subsize;                       /* num of elements for working process except the last one */

		tid = omp_get_thread_num();        /* get current thread ID in this parallel region */
		nthreads = omp_get_num_threads();  /* get total number of threads in this parallel region */

  
 
		/* calculate num of integers one thread should compute */
		if (numints < nthreads) 
		{
			subsize = 1;
			if (tid > numints) 
			{
				numelts = 0;
			}
			else 
			{
				numelts = 1;
			}
		}/* num of integer less than num of threads */
		else 
		{
			subsize = numints / nthreads;
			if (tid != nthreads - 1) 
			{
				numelts = subsize;
			}
			else 
			{
				numelts = numints - (nthreads - 1) * subsize;
			}
		}/* num of integer no less than num of threads */

		if (numelts != 0) 
		{
			tid = omp_get_thread_num();
			//printf("\n Program ID: %d",tid);
			srand(tid + time(NULL));    /* Seed rand functions */
			for (int i = tid * subsize; i < tid * subsize + numelts; i++) 
			{
				integers[i] = i + 1;//rand();
			}
		}/* generate random ints */

	}/* parallel generate random ints */

	/*----------------------------------------------------------
	 * print time elapsed
	 *--------------------------------------------------------*/
	gettimeofday(&genend, &tzp);
	printElapsed("\nGenerating Integers  ", &genstart, &genend, 1);

	gettimeofday(&tmstart, &tzp);
    /*---------------------------------------------------------
     * parallel compute prefix sums
     *--------------------------------------------------------*/

#pragma omp parallel 
	{
		int tid;                            
		int numelts;                       /* num of elements one thread computes */
		int nthreads;                      /* total number of threads requested */
		int subsize;                       /* maximum num of elements for working process */

		tid = omp_get_thread_num();        /* get current thread ID in this parallel region */
		nthreads = omp_get_num_threads();  /* get total number of threads in this parallel region */

		/* calculate num of integers one thread should compute */
		if (numints < nthreads) 
		{
			subsize = 1;
			if (tid > numints) 
			{
				numelts = 0;
			}
			else 
			{
				numelts = 1;
			}
		}/* num of integer less than num of threads */
		else 
		{
			subsize = numints / nthreads;
			if (tid != nthreads - 1) 
			{
				numelts = subsize;
			}
			else 
			{
				numelts = numints - (nthreads - 1) * subsize;
			}
		}/* num of integer no less than num of threads */
		if (numelts != 0) 
		{
			for (int h = tid * subsize; h < tid * subsize + numelts; h++) 
			{
		 		while (predec[h]>=0)  
				{
					integers[h] += integers[predec[h]];
					predec[h] = predec[predec[h]];
				}; 
				// if (h) integers[h] += integers[0]
			}
		}

	}/* parallel compute prefix sums */

	/*---------------------------------------------------------
	 * print time elapsed
	 *--------------------------------------------------------*/
	gettimeofday(&tmend, &tzp);
	printElapsed("\nCompute PrefixSum ", &tmstart, &tmend, 1);
	printf("\n");
/*
	printf ("\n");
	for (int i = 0; i < numints; ++i)
    {
		printf ("%d ", integers[i]);
    }
	printf ("\n");
*/
	/*---------------------------------------------------------
	 * cleanup
	 *--------------------------------------------------------*/
	free(integers);
	free(predec);
	return (0);
}/* main() */

